#!/usr/bin/env python
# -*- indent-tabs-mode: nil; tab-width: 4; coding: utf-8 -*-
# vi: set ts=4 sts=4 sw=4 set smarttab set expandtab
# http://www.careercup.com/question?id=14736688
"""
The maximum suffix of a string is the lexicographically largest suffix of the string. The maximum
suffix problem is to find the maximum suffix of a given string. Linear time algorithm required.
"""

import os, re, sys, getopt
import logging
import locale
from utils import *
import copy

@time_profile
def get_max_suffix_david(s):
    if not s: return s
    max_indexes = [i for i in range(0, len(s))]
    max_length = 0
    while len(max_indexes) > 1:
        max_char, new_indexes = -1, []
        for index in max_indexes:
            if index + max_length >= len(s): break
            if s[index + max_length] > max_char:
                new_indexes = []
                new_indexes.append(index)
                max_char = s[index + max_length]
            elif s[index + max_length] == max_char:
                new_indexes.append(index)
        max_length += 1
        max_indexes, pre_index = [], 0
        max_sequences, sequences = 1, 1
        for i, index in enumerate(new_indexes):
            if i == 0: continue
            if index == new_indexes[i - 1] + max_length:
                sequences += 1
            else:
                if sequences > max_sequences:
                    max_indexes, max_sequences = [new_indexes[i - sequences]], sequences
                elif sequences == max_sequences:
                    max_indexes.append(new_indexes[i - sequences])
                sequences = 1
        if sequences == max_sequences:
            max_indexes.append(new_indexes[len(new_indexes) - sequences])
        elif sequences > max_sequences: max_indexes, max_sequences = [new_indexes[len(new_indexes) - sequences]], sequences
        max_length *= max_sequences

        
    return s[max_indexes[0]:]

def max_suffix_duval(a,r0, n):
    r, s, m, d = r0, r0 + 1, 1, 0
    M = [0] * (n + 2)
    M[1] = 1
    while s < n:
        if a[s] < a[s - m]:
            s += 1
            m = s - r
            M[m] = m
        elif a[s] == a[s-m]: 
            s += 1
            M[s - r] = m
        else:
            #print "==>\t",
            #print r, s, m
            #print "==>\t",
            #print M
            d = (s - r ) % m
            if d > 0:
                r = s -d
                m = M[d]
            else:
                r = s
                s += 1
                m = 1
    return a[r:]

@time_profile
def get_max_suffix_lobatt(s):
    return max_suffix_duval(s, 0, len(s))

if __name__ == '__main__':
    for i in range(0, 15):
        arr = random_arr(15, 0, 7)
        s = arr_to_str(arr)
        david, lobatt = get_max_suffix_david(s), get_max_suffix_lobatt(s)
        print s
        if david != lobatt:
            print "FAILed"
            print get_max_suffix_david(s)
            print get_max_suffix_lobatt(s)
        else:
            print "PASS"
        print ""
